package jdt;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import jdt.geom.Circle;
import jdt.geom.ConvexHull;
import jdt.geom.DirectedEdge;
import jdt.geom.Edge;
import jdt.geom.GeometryException;
import jdt.geom.Point;
import jdt.geom.Triangle;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

public class DelaunayTriangulation {

	/* --- Data members --- */

	/** All the points of the triangulation */
	private Set<Point> allPoints = new HashSet<Point>();

	/** True iff all the points of the triangulation falls on the same line */
	private boolean allCollinear = true;

	/** The convex hull of all the points */
	private ConvexHull convexHull = new ConvexHull();;
	
	/** Mapping between edges to the corresponding triangles */
	protected Map<Edge, Set<Triangle>> edgeToTrianglesMap;

	/** The triangles of the triangulation */
	protected Set<Triangle> triangulation;
	
	/* --- Public Methods --- */

	/**
	 * Adds a point to the triangulation.<br>
	 * The point is added iff it wasn't in the triangulation before
	 * 
	 * @param p
	 *            The point to add
	 * @return true iff the point was added
	 */
	public boolean insertPoint(Point p) {
		boolean isAdded = allPoints.add(p);
		if (allCollinear && (allPoints.size() > 2)) {
			Iterator<Point> pointsIterator = allPoints.iterator();
			allCollinear = p.isCollinear(pointsIterator.next(), pointsIterator.next());
		}
		return isAdded;
	}

	/**
	 * Returns the triangles of the triangulation with the bounding triangle
	 * related triangles
	 * 
	 * @return A set of {@link Triangle}s
	 */
	public Set<Triangle> getTriangulation() {
		edgeToTrianglesMap = new HashMap<Edge, Set<Triangle>>();
		triangulation = new HashSet<Triangle>();
		Set<Point> insertedPoints = new HashSet<Point>();
		if (!allCollinear) {
			for (Point p : allPoints) {
				addPointToTriangulation(p, insertedPoints);
			}
		}
		return triangulation;
	}

	/* --- Protected Methods --- */

	/**
	 * Add a new point to a triangulation
	 * 
	 * @param triangulation
	 *            The triangles of the triangulation
	 * @param p
	 *            The point to add
	 * @param insertedPoints All the points which already been inserted to the triangulation
	 */
	protected void addPointToTriangulation(Point p, Set<Point> insertedPoints) {
		insertedPoints.add(p);
		if(insertedPoints.size() < 3){
			convexHull.addPoint(p);
		} else if(insertedPoints.size() == 3){ // The first triangle
			Iterator<Point> pointsToInsertIterator = insertedPoints.iterator();
			Triangle triangle = new Triangle(pointsToInsertIterator.next(),
					pointsToInsertIterator.next(),
					pointsToInsertIterator.next());
			addTriangleToTriangulation(triangle);
			convexHull.addPoint(p);
		} else {
			try {
				Set<Edge> edgesToExtend = convexHull.toBeRemovedUponInsertion(p);
				convexHull.addPoint(p);
				if(edgesToExtend.size() == 0){ // Point inside the convex hull
					List<Triangle> containedTriangles = findContainedTriangles(p);
					if (containedTriangles.size() == 1) {
						handlePointInsideTriangle(containedTriangles.get(0), p);
					} else {
						handlePointOnTwoTriangles(containedTriangles, p);
					}
				} else { // Point extended the convex hull
					Set<Edge> createdEdges = new HashSet<Edge>();
					for (Edge edge : edgesToExtend) {
						Triangle newTriangle = new Triangle(edge, p);
						addTriangleToTriangulation(newTriangle);
						createdEdges.addAll(newTriangle.getEdgeSet());
					}
					
					if(insertedPoints.size() > 3){
						createdEdges.removeAll(edgesToExtend);
						correctTriangulation(createdEdges, edgesToExtend);
					}
				}
			} catch (GeometryException e) {
				// Cann't happen
			}
		}

	}

	/**
	 * Add the bounding triangle to the triangulation
	 */
	protected void addTriangleToTriangulation(Triangle triangle) {
		triangulation.add(triangle);
		for (Edge edge : triangle.getEdgeSet()) {
			updateEdgeToTriangleMap(triangle, edge);
		}
	}

	/**
	 * Flip the argument edge
	 * 
	 * @param edge
	 *            The edge to flip
	 * @param relatedTriangles
	 *            The triangles which share this edge
	 * @return a set of all the edges that may be illegal
	 * @throws GeometryException
	 *             on geometry error
	 */
	protected Set<Edge> flip(Edge edge, List<Triangle> relatedTriangles)
			throws GeometryException {

		if (!relatedTriangles.get(0).getEdgeSet().contains(edge)
				&& !relatedTriangles.get(0).getEdgeSet().contains(edge)) {
			throw new GeometryException("The triangles doesn't share the edge");
		} else {
			Set<Edge> mayBeIllegal = new HashSet<Edge>();
			List<Point> oppositePoints = new ArrayList<Point>(2);

			for (Triangle triangle : relatedTriangles) {
				mayBeIllegal.addAll(triangle.getEdgeSet());
				removeTriangleFromTriangulation(triangle);
				oppositePoints.add(triangle.getOppositeVertex(edge));
			}

			// Create and add the flipped triangles to the triangulation
			Triangle newTriangle1 = new Triangle(oppositePoints.get(0),
					oppositePoints.get(1), edge.getPoints().get(0));
			addTriangleToTriangulation(newTriangle1);

			Triangle newTriangle2 = new Triangle(oppositePoints.get(0),
					oppositePoints.get(1), edge.getPoints().get(1));
			addTriangleToTriangulation(newTriangle2);

			// Add the not-changed edges to the mayBeIllegal set
			Set<Edge> newEdges = Sets.union(newTriangle2.getEdgeSet(),
					newTriangle1.getEdgeSet());
			mayBeIllegal.retainAll(newEdges);
			return mayBeIllegal;
		}
	}

	/* --- Private Methods --- */

	/**
	 * Update the mapping between the edges and triangles with the arguments
	 * 
	 * @param triangle
	 *            The triangle to map to
	 * @param edge
	 *            The edge which should be mapped
	 */
	private void updateEdgeToTriangleMap(Triangle triangle, Edge edge) {
		if (edgeToTrianglesMap.containsKey(edge)) {
			edgeToTrianglesMap.get(edge).add(triangle);
		} else {
			Set<Triangle> mappedTriangles = new HashSet<Triangle>();
			mappedTriangles.add(triangle);
			edgeToTrianglesMap.put(edge, mappedTriangles);
		}
	}

	private void handlePointInsideTriangles(List<Triangle> containedTriangles,
			Point p) throws GeometryException {
		// All the edges before the split
		Set<Edge> oldEdges = new HashSet<Edge>();
		
		// Split the triangles
		Set<Triangle> createdTriangles = new HashSet<Triangle>();
		for (Triangle triangle : containedTriangles) {
			oldEdges.addAll(triangle.getEdgeSet());
			createdTriangles.addAll(triangle.split(p));
			removeTriangleFromTriangulation(triangle);
		}

		Set<Edge> edgesAfterSplit = new HashSet<Edge>();

		// Add the created triangles to the triangulation
		for (Triangle tri : createdTriangles) {
			edgesAfterSplit.addAll(tri.getEdgeSet());
			addTriangleToTriangulation(tri);
		}
		
		// All sure legal edges 
		Set<Edge> definitelyLegalEdges = new HashSet<Edge>(edgesAfterSplit);
		definitelyLegalEdges.removeAll(oldEdges);
		
		// Find potentially illegal edges
		Set<Edge> mayBeIllegalEdges = new HashSet<Edge>(edgesAfterSplit);
		for (Triangle triangle : containedTriangles) {
			mayBeIllegalEdges.retainAll(triangle.getEdgeSet());
		}

		correctTriangulation(definitelyLegalEdges, mayBeIllegalEdges);
	}

	/**
	 * Correct the triangulation using flips if necessary
	 * @param definitelyLegalEdges The edges which are definitely legal
	 * @param mayBeIllegalEdges The edges which may be illegal
	 * @throws GeometryException on flipping exception
	 */
	private void correctTriangulation(Set<Edge> definitelyLegalEdges,
			Set<Edge> mayBeIllegalEdges) throws GeometryException {
		// Flip illegal edges
		while(!mayBeIllegalEdges.isEmpty()){
			Edge edge = mayBeIllegalEdges.iterator().next();
			mayBeIllegalEdges.remove(edge);
			if (!isLegal(edge)) {
				mayBeIllegalEdges.addAll(flip(edge,
						new LinkedList<Triangle>(edgeToTrianglesMap.get(edge))));
			}
			mayBeIllegalEdges.removeAll(definitelyLegalEdges);
			definitelyLegalEdges.add(edge);
		}
	}

	private void handlePointOnTwoTriangles(List<Triangle> containedTriangles,
			Point p) throws GeometryException {
		handlePointInsideTriangles(containedTriangles, p);
	}

	/**
	 * Handle the insertion of a point to inside (not on!) a triangle
	 * 
	 * @param triangulation
	 *            The triangulation
	 * @param triangle
	 *            The triangle contains the point
	 * @param p
	 *            The point to add
	 * @throws GeometryException
	 *             if the point is not inside the triangle
	 */
	private void handlePointInsideTriangle(Triangle triangle, Point p)
			throws GeometryException {
		handlePointInsideTriangles(Collections.singletonList(triangle), p);
	}

	/**
	 * Removes the triangle from the triangulation
	 * 
	 * @param triangle
	 */
	private void removeTriangleFromTriangulation(Triangle triangle) {
		triangulation.remove(triangle);
		for (Edge edge : triangle.getEdgeSet()) {
			Set<Triangle> relatedTriangles = edgeToTrianglesMap.get(edge);
			relatedTriangles.remove(triangle);
			if (relatedTriangles.size() == 0) {
				edgeToTrianglesMap.remove(edge);
			}
		}
	}

	/**
	 * Check if the argument edge is legal in the triangulation
	 * 
	 * @param triangulation
	 *            The triangulation
	 * @param edge
	 *            The edge to check
	 * @return True or false as described
	 */
	private boolean isLegal(Edge edge) {
		return checkCircumCircle(edge);
	}

	/**
	 * For an argument edge, connecting two triangles, checks that the vertex
	 * opposite to the edge in one of the triangles is not inside the
	 * circumcircle of the other triangles
	 * 
	 * @param edge
	 *            The edge to check
	 * @return True iff the vertex is not inside the circumcircle as described
	 */
	private boolean checkCircumCircle(Edge edge) {
		List<Triangle> triangles = new ArrayList<Triangle>(edgeToTrianglesMap.get(edge));
		if(triangles.size() == 2){
			Triangle t1 = triangles.get(0);
			Triangle t2 = triangles.get(1);
			
			List<Point> remainedVertex = new ArrayList<Point>(t2.getVerticesSet());
			remainedVertex.removeAll(t1.getVerticesSet());
			
			Circle circumCircle = t1.getCircumCircle();
			return !circumCircle.contains(remainedVertex.get(0));
		} else {
			return true;
		}
	}

	/**
	 * Find all the triangles in this triangulation which contain the
	 * argument point.<br>
	 * This method assumption is that the argument point is inside atleast one triangle
	 * (meaning not outside the triangulation).
	 * 
	 * @param p
	 *            The point to search for
	 * @return A list of {@link Triangle}s
	 */
	protected List<Triangle> findContainedTriangles(Point p) {
		Triangle nextToSearch = triangulation.iterator().next();

		Set<Triangle> visited = new HashSet<Triangle>();
		while(nextToSearch != null){
			if(visited.contains(nextToSearch)){
				// TODO: this is a known bug. This impects the performance of the triangulation
				List<Triangle> containedTriangles = new ArrayList<Triangle>(2);
				for (Triangle triangle : triangulation) {
					if (triangle.contains(p)) {
						containedTriangles.add(triangle);
					}
				}
				return containedTriangles;
			}
			visited.add(nextToSearch);
			
			// Handle the case in which p is one one of the edges of curr
			for (Edge edge : nextToSearch.getEdgeSet()) {
				if(edge.isOn(p)){
					return new ArrayList<Triangle>(edgeToTrianglesMap.get(edge));
				}
			}

			// Handle the case in which p is inside curr triangle
			if(nextToSearch.contains(p)){
				return Lists.newArrayList(nextToSearch);
			}

			// Handle the case in which p is outside curr triangle
			List<DirectedEdge> clockwizeEdgeList = new ArrayList<DirectedEdge>(nextToSearch.getClockwizeEdgeSet());
			List<DirectedEdge> validEdges = new ArrayList<DirectedEdge>(2);
			
			// Find all the edges which is possible to go through
			for (DirectedEdge directedEdge : clockwizeEdgeList) {
				if(!directedEdge.isRightOf(p)){
					validEdges.add(directedEdge);
				}
			}

			// Select the edge which is closest
			Edge selectedEdge = null;
			if(validEdges.size() == 2){
				double distaneToZero = validEdges.get(0).distance(p);
				double distaneToOne = validEdges.get(1).distance(p);
				if(distaneToZero < distaneToOne){
					selectedEdge = validEdges.get(0).unDirect();
				} else {
					selectedEdge = validEdges.get(1).unDirect();
				}
			} else {
				selectedEdge = validEdges.get(0).unDirect();
			}
			
			Set<Triangle> correspondingTriangles = edgeToTrianglesMap.get(selectedEdge);
			if(correspondingTriangles.size() == 2){
				Iterator<Triangle> trianglesIterator = correspondingTriangles.iterator();
				Triangle firstTriangle = trianglesIterator.next();
				if(!firstTriangle.equals(nextToSearch)){
					nextToSearch = firstTriangle;
				} else {
					nextToSearch = trianglesIterator.next();
				}
			}
		}
		
		// TODO: throw an exception. This can't happen
		return null;
	}
}
